package datastructure.sort;

/**
 * @author yinlei
 * @date 2018/7/3
 * @since 1.0.0
 */
public class HeapSort implements SortMain.Sort {

    @Override
    public void sort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            heapify(a, a.length - i);
            SortUtil.swap(a, 0, a.length - 1 - i);
        }
    }

    private void heapify(int[] a, int length) {
        int count = length / 2;
        for (int i = count - 1; i >= 0; i--) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < length && a[i] < a[left]) {
                SortUtil.swap(a, i, left);
            }
            if (right < length && a[i] < a[right]) {
                SortUtil.swap(a, i, right);
            }
        }
    }
}
